﻿using System;
using System.Collections.Generic;
using Algoritmia.Problems.ExactCover;
using DLinks = Algoritmia.Problems.ExactCover.DLX;
using Algoritmia.Utils;
using Lists = Algoritmia.DataStructures.Lists;
using System.Linq;
using Algoritmia.Schemes;

namespace Algoritmia.Problems.Puzzles.Polyominoes.DLX
{
    public class PolyominoesSolver
    {
        private readonly BacktrackingEnumerator<DLinks.State, DLinks.Cell, DLinks.State> _enumerator;
        private readonly Func<Lists.IList<Lists.IList<int>>> _createMatrix;
        private readonly Func<Lists.IList<Tuple<char, IEnumerable<Tuple<int, int>>, int, int>>> _createRowsCoding;

        public PolyominoesSolver(Func<Lists.IList<Lists.IList<int>>> createMatrix = null,
                                 Func<Lists.IList<Tuple<char, IEnumerable<Tuple<int, int>>, int, int>>> createRowsCoding = null)
        {
            _createMatrix = createMatrix ?? (() => AlgoritmiaFactory.Lists<Lists.IList<int>>.Default);
            _createRowsCoding = createRowsCoding ??
                                (() => AlgoritmiaFactory.Lists<Tuple<char, IEnumerable<Tuple<int, int>>, int, int>>.Default);
            _enumerator = new BacktrackingEnumerator<DLinks.State, DLinks.Cell, DLinks.State>(createSolution: (space, i, d, f) => f);
        }

        public string Solve(string board, Lists.IList<Tuple<char, IEnumerable<IEnumerable<Tuple<int,int>>>>> polyominoes)
        {
            Lists.IList<Lists.IList<int>> matrix;
            Lists.IList<Tuple<char, IEnumerable<Tuple<int, int>>, int, int>> rowsCoding;
            PolyominoesToMatrix(board, polyominoes, out matrix, out rowsCoding);
            var space = new DLX1StateSpace(matrix);
            var selectedRows = _enumerator.First(space);
            return SolutionAsString(selectedRows, board, rowsCoding);
        }

        private void PolyominoesToMatrix(string board, Lists.IList<Tuple<char, IEnumerable<IEnumerable<Tuple<int, int>>>>> polyominoes, out Lists.IList<Lists.IList<int>> matrix,
            out Lists.IList<Tuple<char, IEnumerable<Tuple<int, int>>, int, int>> rowsCoding)
        {
            var polyominoColumn = new Dictionary<char,int>();
            var column = 0;

            foreach(var polyomino in polyominoes)
            {
                var symbol = polyomino.Item1;
                var pieces = polyomino.Item2;
                polyominoColumn[symbol] = column;
                column++;
            }

            var newBoard = board.Split('\n').Select(e => e.ToArray()).ToArray();

            var xyColumn = new Dictionary<Tuple<int,int>, int>();

            for(int y = 0; y < newBoard.Length; y++)
            {
                for(int x = 0; x < newBoard[y].Length; x++)
                {
                    if (newBoard[y][x] == '.')
                    {
                        xyColumn[new Tuple<int, int>(x, y)] = column;
                        column++;
                    }
                }       
            }

            matrix = _createMatrix();
            rowsCoding = _createRowsCoding();

            foreach(var polyomino in polyominoes)
            {
                var symbol = polyomino.Item1;
                var pieces = polyomino.Item2;
                foreach(var piece in pieces)
                {
                    for(int y = 0; y < newBoard.Length; y++)
                    {
                        for(int x = 0; x < newBoard[y].Length; x++)
                        {
                            if ( piece.All( tp => tp.Item1+x >= 0 &&  tp.Item1+x < newBoard[y].Length &&
                                                  tp.Item2+y >= 0 &&  tp.Item2+y < newBoard.Length &&
                                                  newBoard[tp.Item2+y][tp.Item1+x] == '.'))
                            {
                                rowsCoding.Add(new Tuple<char, IEnumerable<Tuple<int, int>>, int, int>(symbol,piece,x,y));
                                matrix.Add(new[] { polyominoColumn[symbol] }.ToAlgoritmiaList());
                                foreach(var tple in piece)
                                {
                                    matrix.Last().Add(xyColumn[new Tuple<int, int>(x+tple.Item1,y+tple.Item2)]);
                                }
                            }
                        }
                    }
                }
            }
        }

        private static string SolutionAsString(DLinks.State selectedRows, string board, Lists.IList<Tuple<char, IEnumerable<Tuple<int, int>>, int, int>> rowsCoding)
        {
            var newBoard = board.Split('\n').Select(e => e.ToArray()).ToArray();
            foreach(var selectedRow in selectedRows.Selected)
            {
                var tuple = rowsCoding[selectedRow];
                var symbol = tuple.Item1;
                var piece = tuple.Item2;
                var x = tuple.Item3;
                var y = tuple.Item4;
                foreach(var point in piece)
                {
                    var i = point.Item1;
                    var j = point.Item2;
                    newBoard[y + j][x + i] = symbol;
                }
            }
            return string.Join("\n", newBoard.Select(r => string.Join("", r))).Replace('*',' ') + "\n";
        }

    }
}
